package leetCodetest

import (
	"math"
	"strings"
)

/**
633. 平方数之和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False
*/
func main() bool {
	return false
}

// for 看两个加数是否可以开平方
func judgeSquareSum2(c int) bool {
	if c == 0 || c == 1 || c == 2 {
		return true
	}
	for i := 0; i*i <= c; i++ {
		//这个数的平方根是整数
		f := math.Sqrt(float64(c - i*i))
		//c-i的平方根是整数
		if f-float64(int(f)) == 0 {
			return true
		}
	}
	return false
}

// for 看两个加数是否可以开平方
func judgeSquareSum(c int) bool {
	if c == 0 || c == 1 || c == 2 {
		return true
	}
	var i int
	k := int(math.Sqrt(float64(c)))
	for i = 0; i <= int(k); i++ {
		sum := i*i + k*k
		if sum == c {
			return true
		} else {

		}
	}
	return false
}

/**
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
输入：
[1,1,2,3,3]
输出：
[1,3,3]
预期结果：
[1,2,3]
*/
func deleteDuplicates2(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	value := head.Val
	tmp := head
	node := head
	for {
		if node.Next == nil {
			break
		}
		next := node.Next
		if next.Val == value {
			//需要舍去这个节点
			tmp.Next = nil
		} else {
			value = next.Val
			tmp.Next = next
			tmp = next
		}
		node = next
	}
	return head
}

type ListNode struct {
	Val  int
	Next *ListNode
}

//套娃算法公式和终止条件
// 终止条件 head == nil
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	head.Next = deleteDuplicates(head.Next)
	nextVal := head.Next.Val
	if head.Val == nextVal {
		head = head.Next
	}
	return head
}

/**
258. 各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
*/
func addDigits(num int) int {
	if num == 0 {
		return 0
	}
	if num%9 == 0 {
		return 9
	} else {
		return num % 9
	}
	//return num % 9 == 0 ?0: num % 9
}

//'Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
给定一个二叉树，返回它的中序 遍历。
输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]
*/
func inorderTraversal(root *TreeNode) []int {
	var res [1024]int
	i := 0
	if root == nil {
		return nil
	}
	degui(root, &res, &i)
	return res[0:i]
}
func degui(node *TreeNode, res *[1024]int, i *int) {
	if node.Left != nil {
		degui(node.Left, res, i)
	}
	(*res)[(*i)] = node.Val
	(*i)++
	if node.Right != nil {
		degui(node.Right, res, i)
	}
}

/**
643. 子数组最大平均数 I
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例 1:
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
注意:
1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。
*/
//很明显 这个用动态规划可以解决
//明显个屁  还是双指针靠谱一些
func findMaxAverage(nums []int, k int) float64 {
	i := 0
	j := 0
	result := 0
	for ; j < k; j++ {
		result += nums[j]
	}

	max := result
	for j < len(nums) {
		result = result - nums[i] + nums[j]
		j++
		i++
		if result > max {
			max = result
		}
	}
	return float64(max) / float64(k)
}

/**
141. 环形链表
给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
*/
func hasCycle(head *ListNode) bool {
	m := make(map[*ListNode]bool)
	for head != nil {
		if m[head] == true {
			return true
		}
		m[head] = true
		head = head.Next
	}
	return false
}
func hasCycle2(head *ListNode) bool {
	if head == nil {
		return false
	}
	if head.Next == nil {
		return false
	}
	slow := head
	faster := head.Next.Next
	for faster != nil {
		if slow == faster {
			return true
		}
		if faster.Next == nil {
			return false
		}
		faster = faster.Next.Next
		slow = slow.Next
	}
	return false
}

/**
1189. “气球” 的最大数量
给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
示例 1：
输入：text = "nlaebolko"
输出：1

示例 2：
输入：text = "loonbalxballpoon"
输出：2

示例 3：
输入：text = "leetcode"
输出：0
提示：
1 <= text.length <= 10^4
text 全部由小写英文字母组成
*/
func maxNumberOfBalloons(text string) int {
	m := make(map[byte]int)
	balloon := "balloon"
	for i := 0; i < len(text); i++ {
		if strings.Contains(balloon, string(text[i])) {
			m[text[i]] = m[text[i]] + 1
		}
	}
	if m['l'] > 0 {
		m['l'] = (m['l']) / 2
	}
	if m['o'] > 0 {
		m['o'] = (m['o']) / 2
	}
	result := m['b']
	for i := 0; i < 7; i++ {
		if result > m[balloon[i]] {
			result = m[balloon[i]]
		}

	}
	return result
}

/**
530. 二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：

   1
    \
     3
    /
   2

输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
*/

func getMinimumDifference(root *TreeNode) int {
	ans, pre := math.MaxInt64, -1
	var digui func(*TreeNode)
	digui = func(node *TreeNode) {
		if node == nil {
			return
		}
		digui(node.Left)
		if pre != -1 && node.Val-pre < ans {
			ans = node.Val - pre
		}
		pre = node.Val
		digui(node.Right)
	}
	digui(root)
	return ans
}

/**
24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]
*/
func swapPairs2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	result := head.Next
	var father *ListNode = nil
	var digui func(*ListNode, *ListNode)
	digui = func(node *ListNode, father *ListNode) {
		if node == nil || node.Next == nil {
			return
		}
		if father != nil {
			father.Next = node.Next
		}
		father = node
		tmp := node.Next
		node.Next = node.Next.Next
		tmp.Next = node
		digui(node.Next, father)
	}
	digui(head, father)
	return result
}
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := head.Next
	head.Next = swapPairs(newHead.Next)
	newHead.Next = head
	return newHead
}
func commonChars(A []string) []string {
	// result := []strings.Builder{}
	return nil

}

/**
1002. 查找常用字符
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。
例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：
输入：["bella","label","roller"]
输出：["e","l","l"]
示例 2：
输入：["cool","lock","cook"]
输出：["c","o"]
*/
